<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/%E7%97%95%E8%BF%B9.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/%E7%97%95%E8%BF%B9.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.lug.ustc.edu.cn/css?family=Lato:300,300italic,400,400italic,700,700italic|Gabriola:300,300italic,400,400italic,700,700italic|Arial:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  <script src="/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"tian_yu_ting.gitee.io","root":"/","scheme":"Gemini","version":"7.7.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"mac"},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":true,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="数据的排序是在解决实际问题时经常用到的步骤，也是数据结构的考点之一，下面介绍10种经典的排序方法。">
<meta property="og:type" content="article">
<meta property="og:title" content="Python常用的排序方法">
<meta property="og:url" content="https://tian_yu_ting.gitee.io/Python/Python_id_55.html">
<meta property="og:site_name" content="Yu ting&#39;s blog">
<meta property="og:description" content="数据的排序是在解决实际问题时经常用到的步骤，也是数据结构的考点之一，下面介绍10种经典的排序方法。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/01.png">
<meta property="og:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/02.png">
<meta property="og:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/03.png">
<meta property="og:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/04.png">
<meta property="og:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/06.png">
<meta property="og:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/07.png">
<meta property="article:published_time" content="2020-06-09T14:13:00.000Z">
<meta property="article:modified_time" content="2020-06-09T14:14:21.757Z">
<meta property="article:author" content="Yu ting">
<meta property="article:tag" content="Python">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95/01.png">

<link rel="canonical" href="https://tian_yu_ting.gitee.io/Python/Python_id_55.html">

<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true
  };
</script>

  
  
    <script src="/js/cursor/love.min.js"></script>
  

  <title>Python常用的排序方法 | Yu ting's blog</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

  <script>
    var mobileBtn = function f() {
        var toggleMenu = document.getElementsByClassName("menu-toggle")[0];
        var mobileMenu = document.getElementById("mobile-menu");
        if(toggleMenu.classList.contains("active")){
           toggleMenu.classList.remove("active")
            mobileMenu.classList.remove("active")
        }else{
            toggleMenu.classList.add("active")
            mobileMenu.classList.add("active")
        }
    }
  </script>

   <!-- 不知道是什么玩意 -->
  <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
<link rel="alternate" href="/atom.xml" title="Yu ting's blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" style="background-image:url(/images/14.jpg);background-repeat:no-repeat;background-attachment: fixed;">


  <div class="container use-motion">
    <!-- 网页上方的黑色长线 -->
    <div class="headband"></div>
    
    <!-- 在首页添加github图标 -->
<!--     <a href="https://github.com/h4055874" target="_blank" rel="noopener" class="github-corner" aria-label="View source on GitHub">
      <svg width="80" height="80" viewBox="0 0 250 250" style="fill:#151513; color:#fff; position: absolute; top: 0; border: 0; right: 0;" aria-hidden="true">
        <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path>
        <path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path>
        <path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path>
      </svg>
    </a>
      <style>.github-corner:hover .octo-arm{animation:octocat-wave 560ms ease-in-out}@keyframes octocat-wave{0%,100%{transform:rotate(0)}20%,60%{transform:rotate(-25deg)}40%,80%{transform:rotate(10deg)}}@media (max-width:500px){.github-corner:hover .octo-arm{animation:none}.github-corner .octo-arm{animation:octocat-wave 560ms ease-in-out}}</style> -->
    <!--  -->

    <!-- -->

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <div>
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Yu ting's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">I only for you!</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>标签<span class="badge">66</span></a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-fw fa-th"></i>分类<span class="badge">16</span></a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>归档<span class="badge">171</span></a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-fw fa-user"></i>关于</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
        <!--
        <input id="switch_default" type="checkbox" class="switch_default">
        <label for="switch_default" class="toggleBtn"></label>
        -->
      </li>
  </ul>

<style>
    /*input css begin*/
*{
    -webkit-tap-highlight-color: rgba(0,0,0,0);
}
/* input[type="checkbox"],input[type="radio"]{
    display: none;
    width: 0;
    height: 0;
    visibility: hidden;
} */
input[type="checkbox"]:checked + label:after{
    transition: all 0.3s ease-in;
}
input[type="checkbox"]:not(:checked) + label:after {
    transition: all 0.3s ease-out;
}
input[type="checkbox"]:checked + label,
input[type="checkbox"]:not(:checked) + label{
    transition: all 0.3s ease-in-out;
}
input[type="checkbox"]:checked + label:before,input[type="checkbox"]:checked + label i:before,input[type="checkbox"]:not(:checked) + label i:before,
input[type="checkbox"]:checked + label i:after,input[type="checkbox"]:not(:checked) + label i:after,input[type="checkbox"]:not(:checked) + label:before{
    transition: all 0.3s ease-in-out;
}
input[type="radio"]:checked + label:after,
input[type="radio"]:not(:checked) + label:after {
    transition: all 0.3s ease-in-out;
}
.switch_default[type="checkbox"]{
    display: none;
}
.switch_default + label{
     background-color: #e6e6e6;
     border-radius:7px;
     cursor: pointer;
     display: inline-block;
     height: 14px;
     position: relative;
     box-shadow: 0.2px 0.2px 1px 0.5px rgb(180,180,180);
     width: 30px;
 }
.switch_default + label:after{
    background-color: #fff;
    border-radius: 50%;
    content: "";
    height: 12px;
    left: 1px;
    position: absolute;
    top: .5px;
    width: 12px;
    box-shadow: 0.2px 0.2px 1px 0.5px rgb(180,180,180);
}
.switch_default:checked + label{
    background-color: #1ABC9C;
    box-shadow:none;
}
.switch_default:checked + label:after{
    left: 17px;
}
</style>
</nav>
  <div class="site-search">
    <div class="search-pop-overlay">
  <div class="popup search-popup">
      <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocorrect="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

  </div>
</div>

  </div>
</div>
    </header>

    <!-- -->
    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>


    <main class="main">
    <!--sm -->
      <div class="main-inner">
        <div class="content-wrap">
          


          <div class="content">
            

  <div class="posts-expand">
      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block " lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://tian_yu_ting.gitee.io/Python/Python_id_55.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.png">
      <meta itemprop="name" content="Yu ting">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Yu ting's blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          Python常用的排序方法
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2020-06-09 22:13:00 / 修改时间：22:14:21" itemprop="dateCreated datePublished" datetime="2020-06-09T22:13:00+08:00">2020-06-09</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Python/" itemprop="url" rel="index"><span itemprop="name">Python</span></a>
                </span>
            </span>

          
            <span id="/Python/Python_id_55.html" class="post-meta-item leancloud_visitors" data-flag-title="Python常用的排序方法" title="阅读次数">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span class="leancloud-visitors-count"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/Python/Python_id_55.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/Python/Python_id_55.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="fa fa-file-word-o"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>5.3k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="fa fa-clock-o"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>5 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <p>　　数据的排序是在解决实际问题时经常用到的步骤，也是数据结构的考点之一，下面介绍10种经典的排序方法。</p>
<a id="more"></a>

<p>　　首先，排序方法可以大体分为插入排序、选择排序、交换排序、归并排序和桶排序四大类，其中，插入排序又分为直接插入排序、二分插入排序和希尔排序，选择排序分为直接选择排序和堆排序，交换排序分为冒泡排序和快速排序，桶排序以基数排序和计数排序为代表。这些排序方法的时间复杂度和空间复杂度分别如下表所示。</p>
<img src="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python排序方法/01.png">

<p>排序方法的稳定性是这样定义的：在待排序序列中如果存在a[i]和a[j]，a[i]=a[j]&amp;&amp;i&lt;j，如果排序后仍然符合a[i]=a[j]&amp;&amp;i&lt;j，即它们的前后相对位置关系没有改变，该排序算法就是稳定的。</p>
<h3 id="1、直接插入排序"><a href="#1、直接插入排序" class="headerlink" title="1、直接插入排序"></a>1、直接插入排序</h3><p>插入排序的基本思想是将数据插入合适的位置。如下所示序列[6,8,1,4,3,9,5,0]，以升序排列为例。</p>
<p>a.6&lt;8，符合升序</p>
<p>b. 8&gt;1，不符合要求，改变1的位置。首先比较1和8，1更小，交换1和8的位置，序列成为[6,1,8,4,3,9,5,0]，然后继续比较1和6，1更小，交换1和6的位置，序列成为[1,6,8,4,3,9,5,0],注意此时前三个值已经符合升序的要求。</p>
<p>c. 8&gt;4，不符合要求，改变4的位置，按照上面的方法，依次与前面的值比较，分别与8和6交换位置，当比较到1时，1&lt;4，不用交换位置。此时序列成为[1,4,6,8,3,9,5,0]</p>
<p>d.重复上满的操作，直到整个序列遍历完成。</p>
<img src="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python排序方法/02.png">

<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">insert_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len(arr)<span class="number">-1</span>):</span><br><span class="line">        <span class="keyword">if</span> arr[i+<span class="number">1</span>]&lt;arr[i]:<span class="comment">#如果arr[i+1]较小，将其插入到前面升序序列中</span></span><br><span class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> range(i+<span class="number">1</span>,<span class="number">0</span>,<span class="number">-1</span>):</span><br><span class="line">                <span class="keyword">if</span> arr[j]&lt;arr[j<span class="number">-1</span>]:<span class="comment">#依次将大于arr[i+1]的值向后移动，直到找到不大于arr[i+1]的值</span></span><br><span class="line">                    arr[j<span class="number">-1</span>],arr[j]=arr[j],arr[j<span class="number">-1</span>]</span><br><span class="line">                <span class="keyword">else</span>:</span><br><span class="line">                    <span class="keyword">break</span></span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure>

<h3 id="2、二分插入排序"><a href="#2、二分插入排序" class="headerlink" title="2、二分插入排序"></a>2、二分插入排序</h3><p>二分插入排序的思想与直接插入排序相同，只是在将数据插入有序序列时，采用了二分查找的思想，即先于中间位置的值进行比较，以缩短查找的时间。代码如下</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">BinaryInsert_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>,len(arr)):</span><br><span class="line">        <span class="keyword">if</span> arr[i]&lt;arr[i<span class="number">-1</span>]:</span><br><span class="line">            left,right=<span class="number">0</span>,i<span class="number">-1</span></span><br><span class="line">            <span class="keyword">while</span> left&lt;right:<span class="comment">#最终right位置的值是有序序列中第一个不大于arr[i]的值</span></span><br><span class="line">                mid=left+(right-left)//<span class="number">2</span></span><br><span class="line">                <span class="keyword">if</span> arr[i]&lt;arr[mid]:<span class="comment">#</span></span><br><span class="line">                    right=mid</span><br><span class="line">                <span class="keyword">else</span>:</span><br><span class="line">                    left=mid+<span class="number">1</span></span><br><span class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> range(i,right,<span class="number">-1</span>):</span><br><span class="line">                arr[j],arr[j<span class="number">-1</span>]=arr[j<span class="number">-1</span>],arr[j]</span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure>

<h3 id="3、希尔排序"><a href="#3、希尔排序" class="headerlink" title="3、希尔排序"></a>3、希尔排序</h3><p>希尔排序建立在直接插入排序的基础上，假设序列长度为n，先取一个小于n的整数d1，序列中所有距离为d1的数据为一组，如下图中，以2为i增量，1，4，5为一组，8，3，0为一组，1，9为1组，然后在组内进行直接插入排序，然后取整数d2,d2&lt;d1，重复上面的步骤，直到增量减少为1。一般的初次取序列的一半为增量，以后每次减半。这样通过相隔增量的数，使得数移动时能跨过多个元素，加快速度。代码如下</p>
<img src="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python排序方法/03.png">

<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">Hill_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    d=len(arr)//<span class="number">2</span></span><br><span class="line">    <span class="keyword">while</span>(d&gt;=<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(len(arr)//d):</span><br><span class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> range(i,len(arr)-d,d):</span><br><span class="line">                <span class="keyword">if</span> arr[j+d]&lt;arr[j]:</span><br><span class="line">                    <span class="keyword">for</span> k <span class="keyword">in</span> range(j+d,i,-d):</span><br><span class="line">                        <span class="keyword">if</span> arr[k]&lt;arr[k-d]:</span><br><span class="line">                            arr[k],arr[k-d]=arr[k-d],arr[k]</span><br><span class="line">        d=d//<span class="number">2</span></span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure>

<p>因为希尔排序跨距离访问元素，因此不稳定。空间复杂度为O(1)，最好的时间复杂度为O(n)。</p>
<h3 id="4、直接选择排序"><a href="#4、直接选择排序" class="headerlink" title="4、直接选择排序"></a>4、直接选择排序</h3><p>选择排序的思想是每次从无序的序列中选择最大或最小的值，并与第一个位置的值交换。如序列l，如果是升序排列，第一次找出l的最小值与l[0]交换，第二次找出l[1:]最小的值，与l[2]交换，以此类推，代码如下。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">select_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len(arr)<span class="number">-1</span>):</span><br><span class="line">        minnum=arr[i]</span><br><span class="line">        m=i</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(i+<span class="number">1</span>,len(arr)):</span><br><span class="line">            <span class="keyword">if</span> arr[j]&lt;minnum:</span><br><span class="line">                minnum=arr[j]</span><br><span class="line">                m=j</span><br><span class="line">        arr[i],arr[m]=arr[m],arr[i]</span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure>

<p>直接选择排序是稳定的，空间复杂度为O(1)，时间复杂度恒定为O(n2),因为原序列是否有序不会影响选择排序的步骤。</p>
<h3 id="5、堆排序"><a href="#5、堆排序" class="headerlink" title="5、堆排序"></a>5、堆排序</h3><p>堆排序用到了大顶堆和小顶堆的概念。大顶堆是父节点最大的二叉树，即arr[i]&gt;=arr[2<em>i+1]&amp;&amp;arr[i]&gt;=arr[2</em>i-1]；小顶堆是父节点的值最小的二叉树，即arr[i]&lt;=arr[2<em>i+1]&amp;&amp;arr[i]&lt;=arr[2</em>i-1]。</p>
<p>以升序排序为例，首先建立初始最大堆，以某个节点为入口，向下调整其子节点，使其符合大顶堆的特点。建立初始大顶堆的过程会重复调整一些节点，是因为父节点和子节点的交换，会影响以子节点为根节点的子树，如图中，[9,1,7]子树原符合要求，6和9交换后，[6,1,7]不符合要求，就要再次调整该子树。</p>
<p>初始大顶堆建立之后，将根节点的值置换到序列末尾，然后重新调整前面的序列，这时只从根节点向下调整即可，因为初始大顶堆已经形成，如图中，即便交换了0和4的位置，父节点8也仍旧是最大的。</p>
<img src="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python排序方法/04.png">

<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">heap_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">adjust</span><span class="params">(arr,node,maxid)</span>:</span></span><br><span class="line">        root=node</span><br><span class="line">        <span class="keyword">while</span> <span class="literal">True</span>:</span><br><span class="line">            child=<span class="number">2</span>*root+<span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span> child&gt;maxid:</span><br><span class="line">                <span class="keyword">return</span> </span><br><span class="line">            child=child+<span class="number">1</span> <span class="keyword">if</span> arr[child+<span class="number">1</span>]&gt;arr[child] <span class="keyword">and</span> child+<span class="number">1</span>&lt;maxid <span class="keyword">else</span> child<span class="comment">#child是两个孩子中值较大的一个</span></span><br><span class="line">            <span class="keyword">if</span> arr[root]&lt;arr[child]:</span><br><span class="line">                arr[root],arr[child]=arr[child],arr[root]</span><br><span class="line">                root=child</span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                <span class="keyword">return</span> </span><br><span class="line">    first=len(arr)//<span class="number">2</span><span class="number">-1</span></span><br><span class="line">    <span class="keyword">for</span> node <span class="keyword">in</span> range(first,<span class="number">-1</span>,<span class="number">-1</span>):</span><br><span class="line">        adjust(arr,node,len(arr)<span class="number">-1</span>)</span><br><span class="line">    <span class="keyword">for</span> maxid <span class="keyword">in</span> range(len(arr)<span class="number">-1</span>,<span class="number">0</span>,<span class="number">-1</span>):</span><br><span class="line">        arr[<span class="number">0</span>],arr[maxid]=arr[maxid],arr[<span class="number">0</span>]</span><br><span class="line">        adjust(arr,<span class="number">0</span>,maxid<span class="number">-1</span>)</span><br></pre></td></tr></table></figure>

<p>堆排序不稳定，空间复杂度为O(1)，但时间复杂度恒定为O(nlogn)。</p>
<h3 id="6、冒泡排序"><a href="#6、冒泡排序" class="headerlink" title="6、冒泡排序"></a>6、冒泡排序</h3><p>交换排序即通过交换元素位置，使序列有序。冒泡排序是最简单的交换排序，每次将最大值/最小值依次交换到序列末尾。冒泡排序是稳定的，空间复杂度为O(1)，时间复杂度最好为O(n)。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bubble_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len(arr)<span class="number">-1</span>):    <span class="comment"># 这个循环负责设置冒泡排序进行的次数</span></span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(len(arr)-i<span class="number">-1</span>):  <span class="comment"># ｊ为列表下标</span></span><br><span class="line">            <span class="keyword">if</span> arr[j] &gt; arr[j+<span class="number">1</span>]:</span><br><span class="line">                arr[j], arr[j+<span class="number">1</span>] = arr[j+<span class="number">1</span>], arr[j]</span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure>

<h3 id="7、快速排序"><a href="#7、快速排序" class="headerlink" title="7、快速排序"></a>7、快速排序</h3><p>快速排序可以说是使用频率和考察频率最高的排序方法。快速排序的基本思想是以序列中的某个值为标准，大于该值的被放在右边，小于该值放在左边，然后再继续对该值左右两两边的序列重复此步骤，思想很简单，代码如下。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">quick_sort</span><span class="params">(arr,start,end)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> end-start&lt;=<span class="number">0</span>: <span class="keyword">return</span> </span><br><span class="line">    index=random.randrange(start,end+<span class="number">1</span>)</span><br><span class="line">    print(index)</span><br><span class="line">    arr[end],arr[index]=arr[index],arr[end]</span><br><span class="line">    small=start<span class="number">-1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(start,end):</span><br><span class="line">        <span class="keyword">if</span> arr[i]&lt;arr[end]:</span><br><span class="line">            small+=<span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span> small!=i:<span class="comment">#如果small与i不相同，说明有大于arr[end]的值出现，small记录的是分界线的位置</span></span><br><span class="line">                arr[i],arr[small]=arr[small],arr[i]</span><br><span class="line">    small+=<span class="number">1</span></span><br><span class="line">    arr[end],arr[small]=arr[small],arr[end]</span><br><span class="line">    print(arr)</span><br><span class="line">    quick_sort(arr,start,small<span class="number">-1</span>)</span><br><span class="line">    quick_sort(arr,small+<span class="number">1</span>,end)</span><br></pre></td></tr></table></figure>

<p>对于python，有一种更加简单明了的实现方式</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">qsort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> len(arr) &lt;= <span class="number">1</span>: <span class="keyword">return</span> arr</span><br><span class="line">    <span class="keyword">return</span> qsort([lt <span class="keyword">for</span> lt <span class="keyword">in</span> arr[<span class="number">1</span>:] <span class="keyword">if</span> lt &lt; arr[<span class="number">0</span>]]) + arr[<span class="number">0</span>:<span class="number">1</span>]+ qsort([ge <span class="keyword">for</span> ge <span class="keyword">in</span> arr[<span class="number">1</span>:] <span class="keyword">if</span> ge &gt;= arr[<span class="number">0</span>]])</span><br></pre></td></tr></table></figure>

<p>快速排序并没有创建新的数组，但由于实现过程中利用了函数的递归调用，需要堆栈空间，所以空间复杂度为O(nlogn)，时间复杂度最好为O(nlogn)。</p>
<h3 id="8、归并排序"><a href="#8、归并排序" class="headerlink" title="8、归并排序"></a>8、归并排序</h3><p>归并排序采用分而治之的思想，将序列分为多个小的序列，对小的序列排序之后，将小序列合并为大的序列，过程如下图所示。</p>
<img src="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python排序方法/06.png">

<p>归并排序需要新的数组存放合并后的序列，空间复杂度为O(n)，时间复杂度恒定为O(nlogn)，是稳定的。</p>
<h3 id="9、计数排序"><a href="#9、计数排序" class="headerlink" title="9、计数排序"></a>9、计数排序</h3><p>桶排序实际上是一类排序方法的总称。桶排序的思想是将所有数据按照一定的映射关系放到一定数量的桶中，将每个桶里的数据排序，再将所有的桶组合起来，所以不同的映射关系下可以产生不同的桶排序，并且桶排序是基于其他排序算法的，桶内数据的排序需要使用其他排序算法。计数排序和基数排序是桶排序的两种代表。</p>
<p>计数排序是采用的映射关系是最直接的f[i]=i，即一个桶里的数字都是相同的，因此没有桶内排序的步骤。具体过程为，</p>
<p>1.找出待排序的数组中最大和最小的元素<br>2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项，这时映射的过程<br>3.对所有的计数累加，C[i]的含义即是在数组中小于i的元素个数，即为排序后i应放的位置<br>4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个 元素就将C(i)减去1。</p>
<p>代码如下</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">count_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    crr=[]</span><br><span class="line">    m=max(arr)+<span class="number">1</span></span><br><span class="line">    ll=len(arr)</span><br><span class="line">    ans=[]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(ll):<span class="comment">#用于存放排序后的数组</span></span><br><span class="line">        ans.append(<span class="literal">None</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(m):<span class="comment">#桶</span></span><br><span class="line">        crr.append(<span class="number">0</span>)</span><br><span class="line">    <span class="keyword">for</span> num <span class="keyword">in</span> arr:<span class="comment">#映射的过程，计数</span></span><br><span class="line">        crr[num]+=<span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>,m):<span class="comment">#计数累加</span></span><br><span class="line">        crr[i]=crr[i<span class="number">-1</span>]+crr[i]</span><br><span class="line">    <span class="keyword">for</span> num <span class="keyword">in</span> arr:<span class="comment">#反向填充数组</span></span><br><span class="line">        ans[crr[num]<span class="number">-1</span>]=num</span><br><span class="line">        crr[num]-=<span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> ans</span><br></pre></td></tr></table></figure>

<h3 id="10、基数排序"><a href="#10、基数排序" class="headerlink" title="10、基数排序"></a>10、基数排序</h3><p>基数排序的映射方法是按照数据特定位上数字放入不同的桶中， 将序列中的数组按照个位放到不同的桶中，然后按照个位0~9的顺序依次取出，再按照十位放到不同的桶中，…….直到达到数据的最高位，最后一次将数据取出时，排序完成，例如：</p>
<img src="https://gitee.com/tian_yu_ting/blog_img/raw/master/Python排序方法/07.png">

<p>实现代码</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">radix_sort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">compare</span><span class="params">(basis,arr)</span>:</span><span class="comment">#以数组basis为依据的插入排序</span></span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>,len(basis)):</span><br><span class="line">            <span class="keyword">if</span> basis[i]&lt;basis[i<span class="number">-1</span>]:</span><br><span class="line">                <span class="keyword">for</span> j <span class="keyword">in</span> range(i,<span class="number">0</span>,<span class="number">-1</span>):</span><br><span class="line">                    <span class="keyword">if</span> basis[j<span class="number">-1</span>]&gt;basis[j]:</span><br><span class="line">                        basis[j],basis[j<span class="number">-1</span>]=basis[j<span class="number">-1</span>],basis[j]</span><br><span class="line">                        arr[j],arr[j<span class="number">-1</span>]=arr[j<span class="number">-1</span>],arr[j]</span><br><span class="line">                    <span class="keyword">else</span>:</span><br><span class="line">                        <span class="keyword">break</span></span><br><span class="line">    upnum=max(arr)</span><br><span class="line">    tmp=<span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span>(tmp&lt;upnum):</span><br><span class="line">        basis=[num//tmp%<span class="number">10</span> <span class="keyword">for</span> num <span class="keyword">in</span> arr]</span><br><span class="line">        compare(basis,arr)</span><br><span class="line">        tmp*=<span class="number">10</span></span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure>

<p>注意基数排序在桶内排序时，一定要采用稳定的排序方法，这样才可以利用之前的排序结果，否则之前的排序是无意义的。</p>

    </div>

    
    
    

    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束 <i class="fa fa-paw"></i> 感谢您的阅读-------------</div>
    
</div>
      
    </div>
    
    <div>
      
        
<div class="my_post_copyright">
  <script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>
  
  <!-- JS库 sweetalert 可修改路径 -->
  <script src="https://cdn.bootcss.com/jquery/2.0.0/jquery.min.js"></script>
  <script src="https://unpkg.com/sweetalert/dist/sweetalert.min.js"></script>
  <p><span>本文标题:</span><a href="/Python/Python_id_55.html">Python常用的排序方法</a></p>
  <p><span>文章作者:</span><a href="/" title="访问 Yu ting 的个人博客">Yu ting</a></p>
  <p><span>发布时间:</span>2020年06月09日 - 22:06</p>
  <p><span>最后更新:</span>2020年06月09日 - 22:06</p>
  <p><span>原始链接:</span><a href="/Python/Python_id_55.html" title="Python常用的排序方法">https://tian_yu_ting.gitee.io/Python/Python_id_55.html</a>
    <span class="copy-path"  title="点击复制文章链接"><i class="fa fa-clipboard" data-clipboard-text="https://tian_yu_ting.gitee.io/Python/Python_id_55.html"  aria-label="复制成功！"></i></span>
  </p>
  <p><span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank" title="Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)">署名-非商业性使用-禁止演绎 4.0 国际</a> 转载请保留原文链接及作者。</p>  
</div>
<script> 
    var clipboard = new Clipboard('.fa-clipboard');
    $(".fa-clipboard").click(function(){
      clipboard.on('success', function(){
        swal({   
          title: "",   
          text: '复制成功',
          icon: "success", 
          showConfirmButton: true
          });
    });
    });  
</script>

      
    </div>
      
  <div class="popular-posts-header">相关文章推荐</div>
  <ul class="popular-posts">
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="\Flask\Flask_id_01.html" rel="bookmark">flask中app上下文机制</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="\Flask\Flask_id_02.html" rel="bookmark">flask开端</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="\Flask\Flask_id_03.html" rel="bookmark">flask_migrate</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="\Flask\Flask_id_04.html" rel="bookmark">flask_route</a></div>
    </li>
    <li class="popular-posts-item">
      <div class="popular-posts-title"><a href="\Flask\Flask_id_05.html" rel="bookmark">flask_script</a></div>
    </li>
  </ul>

        <div class="reward-container">
  <div>可以请我喝杯咖啡嘛</div>
  <button onclick="var qr = document.getElementById('qr'); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
      
      <div style="display: inline-block;">
        <img src="/images/wechat.jpg" alt="Yu ting 微信支付">
        <p>微信支付</p>
      </div>
      
      <div style="display: inline-block;">
        <img src="/images/alipay.jpg" alt="Yu ting 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>


      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/Python/" rel="tag">分类： Python</a>
          </div>

        
  <div class="post-widgets">
    <div class="wp_rating">
      <div id="wpac-rating"></div>
    </div>
  </div>


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/Redis/Redis_id_06.html" rel="prev" title="Redis的五中数据类型">
      <i class="fa fa-chevron-left"></i> Redis的五中数据类型
    </a></div>
      <div class="post-nav-item">
    <a href="/Python/Python_id_56.html" rel="next" title="Python判断链表是否成环，及找到入环节点">
      Python判断链表是否成环，及找到入环节点 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  

  </div>


              <!-- 此处可在文章模块中间添加东西 -->
          </div>
          <!-- 评论系统 -->
          <!--
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
-->
        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#1、直接插入排序"><span class="nav-text">1、直接插入排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2、二分插入排序"><span class="nav-text">2、二分插入排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3、希尔排序"><span class="nav-text">3、希尔排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4、直接选择排序"><span class="nav-text">4、直接选择排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5、堆排序"><span class="nav-text">5、堆排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6、冒泡排序"><span class="nav-text">6、冒泡排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#7、快速排序"><span class="nav-text">7、快速排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#8、归并排序"><span class="nav-text">8、归并排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#9、计数排序"><span class="nav-text">9、计数排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#10、基数排序"><span class="nav-text">10、基数排序</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Yu ting"
      src="/images/avatar.png">
  <p class="site-author-name" itemprop="name">Yu ting</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">171</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">16</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">66</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/yourname" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;yourname" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://mail.google.com/mail/u/0/#inbox" title="E-Mail → https:&#x2F;&#x2F;mail.google.com&#x2F;mail&#x2F;u&#x2F;0&#x2F;#inbox" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://weibo.com/u/6207787940" title="Weibo → https:&#x2F;&#x2F;weibo.com&#x2F;u&#x2F;6207787940" rel="noopener" target="_blank"><i class="fa fa-fw fa-weibo"></i>Weibo</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://news.google.com/?hl=zh-HK&gl=HK&ceid=HK%253Azh-Hant" title="Google → https:&#x2F;&#x2F;news.google.com&#x2F;?hl&#x3D;zh-HK&amp;gl&#x3D;HK&amp;ceid&#x3D;HK%3Azh-Hant" rel="noopener" target="_blank"><i class="fa fa-fw fa-google"></i>Google</a>
      </span>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title">
      <i class="fa fa-fw fa-link"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://v3u.cn/" title="https:&#x2F;&#x2F;v3u.cn&#x2F;" rel="noopener" target="_blank">刘悦的技术博客</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="http://www.missbless.cn/" title="http:&#x2F;&#x2F;www.missbless.cn&#x2F;" rel="noopener" target="_blank">ISSAC　LOVELESS</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://www.f322.xyz/" title="https:&#x2F;&#x2F;www.f322.xyz&#x2F;" rel="noopener" target="_blank">逆の神様</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="http://www.wosowoso.com/" title="http:&#x2F;&#x2F;www.wosowoso.com&#x2F;" rel="noopener" target="_blank">素材网</a>
        </li>
    </ul>
  </div>

      </div>
      <div style="width:220px;text-align:center;padding-top:10px;margin-bottom:10px;border-bottom:1px dotted #000;"></div>
      <!-- 数字时钟 -->
      <!-- canvas粒子时钟 https://www.cnblogs.com/xiaohuochai/p/6368039.html
  https://www.html5tricks.com/html5-canvas-dance-time.html
 -->
<div id="">
  <canvas id="canvas" style="width:60%;">
</div>
<script>
(function(){
  var WINDOW_WIDTH = 820;
        var WINDOW_HEIGHT = 250;
        var RADIUS = 7; //球半径
        var NUMBER_GAP = 10; //数字之间的间隙
        var u=0.65; //碰撞能量损耗系数
        var context; //Canvas绘制上下文
        var balls = []; //存储彩色的小球
        const colors = ["#33B5E5","#0099CC","#AA66CC","#9933CC","#99CC00","#669900","#FFBB33","#FF8800","#FF4444","#CC0000"]; //彩色小球的颜色
        var currentNums = []; //屏幕显示的8个字符
        var digit =
                  [
                      [
                          [0,0,1,1,1,0,0],
                          [0,1,1,0,1,1,0],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,0,1,1,0],
                          [0,0,1,1,1,0,0]
                      ],//0
                      [
                          [0,0,0,1,1,0,0],
                          [0,1,1,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [1,1,1,1,1,1,1]
                      ],//1
                      [
                          [0,1,1,1,1,1,0],
                          [1,1,0,0,0,1,1],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,1,1,0],
                          [0,0,0,1,1,0,0],
                          [0,0,1,1,0,0,0],
                          [0,1,1,0,0,0,0],
                          [1,1,0,0,0,0,0],
                          [1,1,0,0,0,1,1],
                          [1,1,1,1,1,1,1]
                      ],//2
                      [
                          [1,1,1,1,1,1,1],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,1,1,0],
                          [0,0,0,1,1,0,0],
                          [0,0,1,1,1,0,0],
                          [0,0,0,0,1,1,0],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,1,1,1,0]
                      ],//3
                      [
                          [0,0,0,0,1,1,0],
                          [0,0,0,1,1,1,0],
                          [0,0,1,1,1,1,0],
                          [0,1,1,0,1,1,0],
                          [1,1,0,0,1,1,0],
                          [1,1,1,1,1,1,1],
                          [0,0,0,0,1,1,0],
                          [0,0,0,0,1,1,0],
                          [0,0,0,0,1,1,0],
                          [0,0,0,1,1,1,1]
                      ],//4
                      [
                          [1,1,1,1,1,1,1],
                          [1,1,0,0,0,0,0],
                          [1,1,0,0,0,0,0],
                          [1,1,1,1,1,1,0],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,1,1,1,0]
                      ],//5
                      [
                          [0,0,0,0,1,1,0],
                          [0,0,1,1,0,0,0],
                          [0,1,1,0,0,0,0],
                          [1,1,0,0,0,0,0],
                          [1,1,0,1,1,1,0],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,1,1,1,0]
                      ],//6
                      [
                          [1,1,1,1,1,1,1],
                          [1,1,0,0,0,1,1],
                          [0,0,0,0,1,1,0],
                          [0,0,0,0,1,1,0],
                          [0,0,0,1,1,0,0],
                          [0,0,0,1,1,0,0],
                          [0,0,1,1,0,0,0],
                          [0,0,1,1,0,0,0],
                          [0,0,1,1,0,0,0],
                          [0,0,1,1,0,0,0]
                      ],//7
                      [
                          [0,1,1,1,1,1,0],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,1,1,1,0],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,1,1,1,0]
                      ],//8
                      [
                          [0,1,1,1,1,1,0],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [1,1,0,0,0,1,1],
                          [0,1,1,1,0,1,1],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,0,1,1],
                          [0,0,0,0,1,1,0],
                          [0,0,0,1,1,0,0],
                          [0,1,1,0,0,0,0]
                      ],//9
                      [
                          [0,0,0,0],
                          [0,0,0,0],
                          [0,1,1,0],
                          [0,1,1,0],
                          [0,0,0,0],
                          [0,0,0,0],
                          [0,1,1,0],
                          [0,1,1,0],
                          [0,0,0,0],
                          [0,0,0,0]
                      ]//:
                  ];

        function drawDatetime(cxt){
            var nums = [];

            context.fillStyle="#005eac"
            var date = new Date();
            var offsetX = 70, offsetY = 30;
            var hours = date.getHours();
            var num1 = Math.floor(hours/10);
            var num2 = hours%10;
            nums.push({num: num1});
            nums.push({num: num2});
            nums.push({num: 10}); //冒号
            var minutes = date.getMinutes();
            var num1 = Math.floor(minutes/10);
            var num2 = minutes%10;
            nums.push({num: num1});
            nums.push({num: num2});
            nums.push({num: 10}); //冒号
            var seconds = date.getSeconds();
            var num1 = Math.floor(seconds/10);
            var num2 = seconds%10;
            nums.push({num: num1});
            nums.push({num: num2});

            for(var x = 0;x<nums.length;x++){
                nums[x].offsetX = offsetX;
                offsetX = drawSingleNumber(offsetX,offsetY, nums[x].num,cxt);
                //两个数字连一块，应该间隔一些距离
                if(x<nums.length-1){
                    if((nums[x].num!=10) &&(nums[x+1].num!=10)){
                        offsetX+=NUMBER_GAP;
                    }
                }
            }

            //说明这是初始化
            if(currentNums.length ==0){
                currentNums = nums;
            }else{
                //进行比较
                for(var index = 0;index<currentNums.length;index++){
                    if(currentNums[index].num!=nums[index].num){
                        //不一样时，添加彩色小球
                        addBalls(nums[index]);
                        currentNums[index].num=nums[index].num;
                    }
                }
            }
            renderBalls(cxt);
            updateBalls();

            return date;
        }

        function addBalls (item) {
            var num = item.num;
            var numMatrix = digit[num];
            for(var y = 0;y<numMatrix.length;y++){
                for(var x = 0;x<numMatrix[y].length;x++){
                    if(numMatrix[y][x]==1){
                        var ball={
                            offsetX:item.offsetX+RADIUS+RADIUS*2*x,
                            offsetY:30+RADIUS+RADIUS*2*y,
                            color:colors[Math.floor(Math.random()*colors.length)],
                            g:1.5+Math.random(),
                            vx:Math.pow(-1, Math.ceil(Math.random()*10))*4+Math.random(),
                            vy:-5
                        }
                        balls.push(ball);
                    }
                }
            }
        }

        function renderBalls(cxt){
            for(var index = 0;index<balls.length;index++){
                cxt.beginPath();
                cxt.fillStyle=balls[index].color;
                cxt.arc(balls[index].offsetX, balls[index].offsetY, RADIUS, 0, 2*Math.PI);
                cxt.fill();
            }
        }

        function updateBalls () {
            var i =0;
            for(var index = 0;index<balls.length;index++){
                var ball = balls[index];
                ball.offsetX += ball.vx;
                ball.offsetY += ball.vy;
                ball.vy+=ball.g;
                if(ball.offsetY > (WINDOW_HEIGHT-RADIUS)){
                    ball.offsetY= WINDOW_HEIGHT-RADIUS;
                    ball.vy=-ball.vy*u;
                }
                if(ball.offsetX>RADIUS&&ball.offsetX<(WINDOW_WIDTH-RADIUS)){

                    balls[i]=balls[index];
                    i++;
                }
            }
            //去除出边界的球
            for(;i<balls.length;i++){
                balls.pop();
            }
        }
        function drawSingleNumber(offsetX, offsetY, num, cxt){
            var numMatrix = digit[num];
            for(var y = 0;y<numMatrix.length;y++){
                for(var x = 0;x<numMatrix[y].length;x++){
                    if(numMatrix[y][x]==1){
                        cxt.beginPath();
                        cxt.arc(offsetX+RADIUS+RADIUS*2*x,offsetY+RADIUS+RADIUS*2*y,RADIUS,0,2*Math.PI);
                        cxt.fill();
                    }
                }
            }
            cxt.beginPath();
            offsetX += numMatrix[0].length*RADIUS*2;
            return offsetX;
        }

        var canvas = document.getElementById("canvas");
        canvas.width=WINDOW_WIDTH;
        canvas.height=WINDOW_HEIGHT;
        context = canvas.getContext("2d");

        //记录当前绘制的时刻
        var currentDate = new Date();

        setInterval(function(){
            //清空整个Canvas，重新绘制内容
            context.clearRect(0, 0, context.canvas.width, context.canvas.height);
            drawDatetime(context);
        }, 50)
})();
</script>

      <!-- 建站时间 -->
      
      
      <!-- 音乐 -->
<!--       <div>
        <audio src="/images/林俊杰 - 对的时间点.flac" autoplay="autoplay" controls="controls" loop="loop"></audio>
        
          <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=298 height=52 src="//music.163.com/outchain/player?type=2&id=569213220&auto=1&height=32"></iframe>
         
      </div> -->
    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-heartbeat" style="color:red"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Yu ting</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
      <span class="post-meta-item-text">站点总字数：</span>
    <span title="站点总字数">420k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span class="post-meta-item-text">站点阅读时长 &asymp;</span>
    <span title="站点阅读时长">6:22</span>
</div>
  <div class="powered-by"><a href="https://weibo.com/u/3035313940" class="theme-link" rel="noopener" target="_blank">Only丶Nie</a>
  </div>
  <span class="post-meta-divider">|</span>
  <div class="powered-by"><a href="https://weibo.com/u/6207787940" class="theme-link" rel="noopener" target="_blank">余生有你才安好丶</a>
  </div>

        
<div class="busuanzi-count">
  <script async src="/js/busuanzi.js"></script>
  <!-- https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js -->
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>总访问人数：
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>人
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>总访问量：
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>次
      </span>
    </span>
</div>







      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js"></script>
  <script src="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>


  <script defer src="/lib/three/three.min.js"></script>


  



  <script>
  if (CONFIG.page.isPost) {
    wpac_init = window.wpac_init || [];
    wpac_init.push({
      widget: 'Rating',
      id    : 24337,
      el    : 'wpac-rating',
      color : 'fc6423'
    });
    (function() {
      if ('WIDGETPACK_LOADED' in window) return;
      WIDGETPACK_LOADED = true;
      var mc = document.createElement('script');
      mc.type = 'text/javascript';
      mc.async = true;
      mc.src = '//embed.widgetpack.com/widget.js';
      var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(mc, s.nextSibling);
    })();
  }
  </script>

  
<script src="/js/local-search.js"></script>













  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : false,
      appId      : 'usjRVOXqGpbFIevxocLk2MXI-gzGzoHsz',
      appKey     : 'xd98ffpeQETblJ8uuGPacjjS',
      placeholder: "请在此处填写评论",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : true,
      lang       : 'zh-cn' || 'zh-cn',
      path       : location.pathname,
      recordIP   : true,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>


  <!-- 动画效果 -->
  

    <!-- 鼠标跟随 -->
  
  <!-- 鼠标指针 -->
  <style>
    body{cursor:url(/images/正常选择.cur),move}
    a{cursor:url(/images/链接选择.cur),wait} 
  </style>

<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"/live2dw/assets/koharu.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":true},"log":false});</script></body>
</html>
